﻿using System;
using System.Collections.Generic;

namespace Project1
{
	/// <summary>
	/// An implementation of the Depth-First-Search algorithm.
	/// </summary>
	public class DepthFirstSearch : AbstractSearch
	{
		/// <summary>
		/// Performs a depth first search
		/// </summary>
		/// <param name="problem">The search problem</param>
		/// <returns>The goal state if a solution exists, otherwise <c>null</c>.</returns>
		protected override State PerformSearch(IProblem problem)
		{
			return DepthLimitedSearch(problem, int.MaxValue).State;
		}

		/// <summary>
		/// Represents the results of a depth-limited search.
		/// </summary>
		protected class DepthLimitedSearchResult
		{
			/// <summary>
			/// The goal state if found, otherwise <c>null</c>.
			/// </summary>
			public State State = null;
			/// <summary>
			/// <c>true</c> if the cutoff limit was reached, otherwise <c>false</c>.
			/// </summary>
			public bool CutOff = false;
		}

		/// <summary>
		/// Performs a depth limited search.
		/// </summary>
		/// <param name="problem">The search problem.</param>
		/// <param name="limit">The cutoff limit.</param>
		/// <returns>Information about whether the goal state was found or if the cutoff was reached.</returns>
		protected DepthLimitedSearchResult DepthLimitedSearch(IProblem problem, int limit)
		{
			//
			// Use a stack for the frontier (this follows rather naturally seeing that we've unrolled the recursive 
			// version of the algorithm)
			//
			Stack<State> frontier = new Stack<State>();
			//
			// Use a hashset for the explored (CLOSED) list
			//
			HashSet<Object> explored = new HashSet<Object>();
			//
			// Is the initial state also the goal state?
			//
			State state = problem.InitialState;
			if (problem.IsGoal(state))
			{
				return new DepthLimitedSearchResult { State = state }; // Problem? There is no problem!
			}
			//
			// Have we reached the cutoff limit?
			//
			if (limit == 0)
			{
				return new DepthLimitedSearchResult { CutOff = true };
			}
			//
			// Place the initial state on the frontier. Then loop until a solution or found, we hit the cutoff limit
			// or the entire search space has been explored.
			//
			frontier.Push(state);
			bool limitHit = false;
			while (true)
			{
				//
				// Have we emptied the frontier?
				//
				if (frontier.Count == 0)
				{
					if (limitHit)
					{
						return new DepthLimitedSearchResult { CutOff = true };
					}
					return new DepthLimitedSearchResult(); // No solution
				}
				//
				// Pop a state/node off the frontier
				//
				state = frontier.Pop();
				//
				// Have we reached the cutoff limit?
				//
				if (state.PathLength > limit)
				{
					limitHit = true;
					//
					// Here we need to clear the explored list. Otherwise the iterative deepening version
					// will not be guaranteed to find an optimal solution.
					//
					explored.Clear();
					//
					// Move on to the next state on the stack/frontier
					//
					continue;
				}
				//
				// Add this state to the explored (CLOSED) list
				//
				explored.Add(state.Key);
				//
				// Performance metric bookkepping
				//
				base.StateExpanded();
				base.SetCurrentTreeSize(state.PathLength + frontier.Count);
				//
				// Iterate through the successor states of the current state
				//
				foreach (State successor in problem.GetSuccessors(state))
				{
					//
					// Skip this state if it's already been explored (expanded), if it's on the current path or 
					// if it's on the frontier
					//
					if (explored.Contains(successor.Key) || frontier.Contains(successor) || state.PathContains(successor))
					{
						continue;
					}
					//
					// Is this the goal state?
					//
					if (problem.IsGoal(successor))
					{
						base.SetCurrentTreeSize(successor.PathLength + frontier.Count + 1);
						return new DepthLimitedSearchResult { State = successor };
					}
					//
					// Add this successor to the frontier
					//
					frontier.Push(successor);
				}
			}
		}
	}
}
